#!/usr/bin/env python
# -*- coding: utf-8 -*-

# @Time     :2022/03/07
# @Author   :Changshu
# @File     :Exercise17.py
# 17. 电话号码的字母组合

def fourSum(nums: list, target: int) -> list:
	res = []
	if not nums or len(nums) < 4:
		return res
	sorted_nums = sorted(nums)
	length = len(sorted_nums)
	for a in range(0, length - 3):
		if a > 0 and sorted_nums[a] == sorted_nums[a - 1]:
			continue
		if sorted_nums[a] + sorted_nums[a + 1] + sorted_nums[a + 2] + sorted_nums[a + 3] > target:
			break
		if sorted_nums[a] + sorted_nums[length - 3] + sorted_nums[length - 2] + sorted_nums[length - 1] < target:
			continue
		for b in range(a + 1, length - 2):
			if b > a + 1 and sorted_nums[b] == sorted_nums[b - 1]:
				continue
			if sorted_nums[a] + sorted_nums[b] + sorted_nums[b + 1] + sorted_nums[b + 2] > target:
				break
			if sorted_nums[a] + sorted_nums[b] + sorted_nums[length - 2] + sorted_nums[length - 1] < target:
				continue
			c, d = b + 1, length - 1
			while d > c:
				s = sorted_nums[a] + sorted_nums[b] + sorted_nums[c] + sorted_nums[d]
				if s == target:
					res.append([sorted_nums[a], sorted_nums[b], sorted_nums[c], sorted_nums[d]])
					while d > c and sorted_nums[c] == sorted_nums[c + 1]:
						c += 1
					c += 1
					while d > c and sorted_nums[d] == sorted_nums[d - 1]:
						d -= 1
					d -= 1
				elif s > target:
					d -= 1
				else:
					c += 1
	return res

def fourSum2(nums: list, target: int) -> list:
        res=[]
        if not nums or len(nums)<4:
            return res
        sorted_nums=sorted(nums)
        for a in range(0,len(sorted_nums)):
            if a!=0 and sorted_nums[a]==sorted_nums[a-1]:
                continue
            d=len(sorted_nums)-1
            for b in range(a+1,len(sorted_nums)):
                if b>=d-1:
                    break
                if b!=a+1 and sorted_nums[b]==sorted_nums[b-1]:
                    continue
                c,t=d-1,d-1
                while c>b+1 and sorted_nums[a]+sorted_nums[b]+sorted_nums[c]+sorted_nums[d]>target:
                    c-=1
                while d>c and sorted_nums[a]+sorted_nums[b]+sorted_nums[c]+sorted_nums[d]>target:
                    d-=1
                if c==d:
                    continue
                if c!=t and d==t+1 and sorted_nums[c]==sorted_nums[c+1]:
                    continue
                if (d==len(sorted_nums)-1 or sorted_nums[d]!=sorted_nums[d+1] ) and sorted_nums[a]+sorted_nums[b]+sorted_nums[c]+sorted_nums[d]==target:
                    res.append([sorted_nums[a],sorted_nums[b],sorted_nums[c],sorted_nums[d]])
        return res